//        https://ac.nowcoder.com/acm/contest/940/B/





#include <iostream>
using namespace std;

int main()
{
    int n, m, k;
    cin >> n >> m;
    k = n;
    for (int i = 1; i < m; i++)
    {
        k *= (n - 1);
        k %= 109;
    }
    cout << k << endl;
    return 0;
}